package work;
import com.sun.xml.internal.bind.v2.schemagen.xmlschema.List;

import java.awt.*;
import java.util.Arrays;
import java.util.Map;
import java.util.Set;

public class HeapSort<T extends Comparable<T>> {
    static String[] arr = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};

    public static void main(String[] args) {
        String[] strings = new String[arr.length + 1];
//        creatHeap(arr, strings);
            sort(arr);

        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(strings));
    }

    public static  void sort(Comparable[] source) {
        Comparable[] heap = new Comparable[source.length + 1];
        creatHeap(source, heap);
        int x = heap.length - 1;
        while (x != 1) {
            exchange(heap, 1, x);
            x--;
            sink(heap, 1, x);
        }
        System.arraycopy(heap,1,source,0,source.length);
    }
    public static boolean less(Comparable[] arr, int i, int j) {
        return arr[i].compareTo(arr[j]) < 0;
    }
    public static void exchange(Comparable[] arr, int i, int j) {
        Comparable comparable = arr[i];
        arr[i] = arr[j];
        arr[j] = comparable;
    }
    private static void creatHeap(Comparable[] arr, Comparable[] heap) {
        System.arraycopy(arr, 0, heap, 1, arr.length);
        for (int i = heap.length / 2; i > 0; i--) {
            sink(heap, i, arr.length);
        }
    }

    private static void sink(Comparable[] arr, int index, int range) {
        if (arr.length <= 1) {
            return;
        }
        if (arr.length == 2) {
            return;
        }
        while (index*2+1 <= range) {
            int max;
            if (index*2<=range){
                max = less(arr,index*2,index*2+1)?index*2+1:index*2;
            }else {
                max=index*2;
            }
            if (!less(arr,index,max)){
                break;
            }
            exchange(arr,index,max);
            index=max;
        }
    }
}
